package algorithm;

import java.util.*;

public class Heap {


    public static void swap(int[] arr, int i, int j){
        int a=arr[i];
        arr[i]=arr[j];
        arr[j]=a;
    }

    //向上大根堆
    public void heapInsert(int[] arr, int index){

        while(arr[index] > arr[(index-1)>>1]){
            swap(arr, index, (index-1)>>1);
            index=(index-1)>>1;
        }
    }

    //向下大根堆
    public static void heapify(int[] arr, int index, int heapSize){

        while((index<<1|1) < heapSize){
            int left = index<<1|1;
            int right = left+1;
            // 左右两个孩子中，谁大，谁把自己的下标给largest
            // 右  ->  1) 有右孩子   && 2）右孩子的值比左孩子大才行
            // 否则，左
            int largest = right < heapSize && arr[left] < arr[right] ? right : left;
            if(arr[index] < arr[largest]){
                swap(arr, index, largest);
                index = largest;
            }else
                break;
        }
    }

    //堆排序
    public static void heapSort(int[] arr){
        for (int i = arr.length-1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }

        int heapSize = arr.length;

        while(heapSize>1){
            swap(arr, 0, --heapSize);
            heapify(arr, 0, heapSize);
        }
    }

    public static void sortedArrDistanceLessK(int[] arr, int k){
        int i=arr.length-k;
        int[] heap = new int[k+1];
        for (int j = arr.length-1, m=0; m < k && m < arr.length-1 ; j--, m++) {
            heap[m] = arr[j];
        }

        for (int j = heap.length-1; j >=0 ; j--) {
            heapify(heap, j, heap.length);
        }

        int n = arr.length-1;
        while(i>=0){
            arr[n--] = heap[0];
            if(i==0)
                break;
            heap[k] = arr[--i];
            swap(heap, 0, heap.length-1);
            heapify(heap, 0, k);
        }
        while (k > 1) {
            swap(heap, 0, --k);
            heapify(heap, 0, k);
            arr[n--] = heap[0];
        }

    }


    public static void sortedArrDistanceLessK2(int[] arr, int k){

        if(arr==null||k==0)
            return;
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index=0;
        for (; index <= Math.min(arr.length-1,k-1); index++) {
            heap.add(arr[index]);
        }

        int i = 0;
        for (; index < arr.length; i++, index++) {
            heap.add(arr[index]);
            arr[i] = heap.poll();
        }
        while(!heap.isEmpty()){
            arr[i++] = heap.poll();
        }
    }

    public static int[] randomArrayNoMoveMoreK(int maxSize, int maxValue, int K) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        // 先排个序
        Arrays.sort(arr);
        // 然后开始随意交换，但是保证每个数距离不超过K
        // swap[i] == true, 表示i位置已经参与过交换
        // swap[i] == false, 表示i位置没有参与过交换
        boolean[] isSwap = new boolean[arr.length];
        for (int i = 0; i < arr.length; i++) {
            int j = Math.min(i + (int) (Math.random() * (K + 1)), arr.length - 1);
            if (!isSwap[i] && !isSwap[j]) {
                isSwap[i] = true;
                isSwap[j] = true;
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        return arr;
    }

    public static void main(String[] args) {



//        int[] arr={2,12,5,4,8,7,9,8,10};
//        heapSort(arr);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.println(arr[i]);
//        }
//
        int[] arr = randomArrayNoMoveMoreK(20, 20, 5);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        System.out.println("---------------");
        sortedArrDistanceLessK2(arr, 5);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
